package cn.edu.zzuli.tree;

public class ThreadedBinaryTreeDemo {

    //线索化二叉树的实现
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        Node root = new Node(1);
        Node node3 = new Node(3);
        Node node8 = new Node(8);
        Node node10 = new Node(10);
        Node node14 = new Node(14);
        Node node6 = new Node(6);
        root.left = node3;
        root.right = node6;
        node3.left = node8;
        node3.right = node10;
        node6.left = node14;
        threadedBinaryTree.setRoot(root);
//        threadedBinaryTree.midOrder(root);
        threadedBinaryTree.threadedNodes();
        threadedBinaryTree.threadedList();


    }

}

class ThreadedBinaryTree {
    //根节点
    private Node root;
    //为了实现线索化，需要创建一个指向前驱结点的一个指针
    private Node pre = null;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 对当前节点进行线索化
     * 中序线索化为例
     * @param node
     */
    public void threadedNodes(Node node) {
        //如果node == null，无法线索化
        if (node == null){
            return;
        }

        //先线索化左子树
        threadedNodes(node.left);
        //线索化当前节点
        //处理前驱节点
        if (node.left == null) {
            //指向前驱节点
            node.left = pre;
            //修改当前节点的左指针类型
            node.leftType = 1;
        }

        //指向后继节点(实际上是在第一次回溯的时候才开始进行)
        //第一次 pre = null，当第一次回溯的时候，这里pre变成了前驱节点
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }

        //最最重要的一条
        pre = node;

        //线索化右子树
        threadedNodes(node.right);
    }

    //遍历线索化二叉树的方法(中序为例)
    public void threadedList() {
        //定义一个变量,存储当前遍历的节点
        Node curNode = root;
        while (curNode != null) {

            //循环找到被线索化的节点 如果节点的leftType == 1，说明是线索化的有效节点
            while (curNode.leftType == 0) {
                curNode = curNode.left;
            }

            System.out.println(curNode);

            //如果当前节点的右指针指向的是后继节点，那么就一直输出。
            while (curNode.rightType == 1) {
                curNode = curNode.right;
                System.out.println(curNode);
            }

            curNode = curNode.right;
        }

    }

}